package com.lihepeng.leecode.sort.partise;

import org.junit.Test;

import java.util.Arrays;

/**
 *
 */
public class TestQuickSort {
    @Test
    public void runTest(){
        int []arrs = {1,7,3,5,0,9,10};
        System.out.println(Arrays.toString(arrs));
        quickSort(arrs);
        System.out.println(Arrays.toString(arrs));
    }

    private void quickSort(int []arrs){
        quickSort(arrs,0,arrs.length-1);
    }

    private void quickSort(int []arrs,int left,int right){
        if (left<right){
            int partition = findPartition(arrs, left, right);
            quickSort(arrs,0,partition-1);
            quickSort(arrs,partition+1,right);
        }
    }
    private int findPartition(int []arr,int left,int right){
        int standVal = arr[left];
        while(left<right){
            while (left <right && arr[right]>standVal){
                right--;
            }
            arr[left] = arr[right];
            while (left <right && arr[left]<=standVal){
                left++;
            }
            arr[right] = arr[left];

        }
        arr[left] = standVal;
        return left;
    }
}

